/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2024-03-11
 * Time:8:39
 */
public class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length,n = matrix[0].length;

        //[i,j]表示到此位置的最小和
        int[][] dp = new int[m+1][n+2];
        for(int i = 1;i <= m;i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n+1] = Integer.MAX_VALUE;
        }
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                dp[i][j] = getMin(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) + matrix[i-1][j-1];
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = 1;i <= n;i++) {
            min = Math.min(min,dp[m][i]);
        }
        return min;
    }

    private int getMin(int x,int y,int z) {
        int min1 = x < y ? x : y;
        return Math.min(min1,z);
    }
    ////////////////////////////////////////////////////
    public static int minPathSum(int[][] grid) {
        int m = grid.length,n = grid[0].length;
        int[][] dp = new int[m+1][n+1];
        for(int i = 0,j = 0;i <= m || j <= n;i++,j++) {
            if(i <= m) grid[0][i] = Integer.MAX_VALUE;
            if(j <= n) grid[j][0] = Integer.MAX_VALUE;
        }
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                dp[i][j] = grid[i-1][j-1] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
    }

}
